package Week1;

import java.util.*;

public class Day4 {
}



//牛客:WY22 Fibonacci数列
// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main9 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int a = 0 , b = 1 , c = 1;
        while(n > c){
            a = b;
            b = c;
            c = a + b;
        }
        System.out.println(Math.min(c-n,n-b));
    }
}

//NC242 单词搜素
class Solution2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board string字符串一维数组
     * @param word string字符串
     * @return bool布尔型
     */
    int m , n;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    boolean[][] visits;
    char[] word;
    public boolean exist (String[] board, String _word) {
        // write code here
        m = board.length;
        n = board[0].length();
        word = _word.toCharArray();
        visits = new boolean[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                //如此时的单词为要搜素单词的第一个单词就可以进行遍历
                if(board[i].charAt(j) == word[0]){
                    //防止再次访问
                    visits[i][j] = true;
                    //深搜
                    if(dfs(board,i,j,1)) return true;
                    visits[i][j] = false;
                }
            }
        }
        return false;
    }

    public boolean dfs(String[] board , int i , int j , int pos){
        if(pos == word.length) return true;
        //扩展的四个方向
        for(int k = 0; k < 4; k++){
            int a = dx[k] + i, b = dy[k] + j;
            //如没有越界，且没有被访问过，同时此时位置的单词为要查找的下一个单词就再进行深搜
            if(a >= 0 && a < m && b >= 0 && b < n && !visits[a][b] && board[a].charAt(b) == word[pos]){
                visits[a][b] = true;
                if(dfs(board,a,b,pos+1)) return true;
                visits[a][b] = false;
            }
        }
        return false;
    }
}

//牛客 BC140 杨辉三角
class Main10 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][]arr = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= i; j++){
                //如果是第0列或者行和列相等此时位置的值就为1
                if(i == j || j == 0){
                    arr[i][j] = 1;
                }else{//上方和左上方相加
                    arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j <=i; j++){
                System.out.printf("%5d" , arr[i][j]);
            }
            System.out.println();
        }
    }
}